{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Remove Zero Sum Consecutive Nodes from Linked List"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #hash-table #linked-list"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #哈希表 #链表"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: removeZeroSumSublists"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #从链表中删去总和值为零的连续节点"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个链表的头节点&nbsp;<code>head</code>，请你编写代码，反复删去链表中由 <strong>总和</strong>&nbsp;值为 <code>0</code> 的连续节点组成的序列，直到不存在这样的序列为止。</p>\n",
    "\n",
    "<p>删除完毕后，请你返回最终结果链表的头节点。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p>你可以返回任何满足题目要求的答案。</p>\n",
    "\n",
    "<p>（注意，下面示例中的所有序列，都是对&nbsp;<code>ListNode</code>&nbsp;对象序列化的表示。）</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>head = [1,2,-3,3,1]\n",
    "<strong>输出：</strong>[3,1]\n",
    "<strong>提示：</strong>答案 [1,2,1] 也是正确的。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>head = [1,2,3,-3,4]\n",
    "<strong>输出：</strong>[1,2,4]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>head = [1,2,3,-3,-2]\n",
    "<strong>输出：</strong>[1]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>给你的链表中可能有 <code>1</code> 到&nbsp;<code>1000</code>&nbsp;个节点。</li>\n",
    "\t<li>对于链表中的每个节点，节点的值：<code>-1000 &lt;= node.val &lt;= 1000</code>.</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [remove-zero-sum-consecutive-nodes-from-linked-list](https://leetcode.cn/problems/remove-zero-sum-consecutive-nodes-from-linked-list/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [remove-zero-sum-consecutive-nodes-from-linked-list](https://leetcode.cn/problems/remove-zero-sum-consecutive-nodes-from-linked-list/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,-3,3,1]', '[1,2,3,-3,4]', '[1,2,3,-3,-2]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeZeroSumSublists(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        def add(hair):\n",
    "            doc = {0: hair}\n",
    "            tem = hair.next\n",
    "            s = 0\n",
    "            while tem:\n",
    "                s += tem.val\n",
    "                if s in doc:\n",
    "                    doc[s].next = tem.next\n",
    "                    return 1\n",
    "                doc[s] = tem\n",
    "                tem = tem.next\n",
    "            return 0\n",
    "        \n",
    "\n",
    "        hair = ListNode(next=head)\n",
    "        while 1:\n",
    "            if not add(hair):\n",
    "                break\n",
    "        return hair.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeZeroSumSublists(self, head: ListNode) -> ListNode:\n",
    "        l = ListNode(0)\n",
    "        l.next = head\n",
    "        d = {0:l}\n",
    "        s = 0\n",
    "        while head:\n",
    "            s+=head.val\n",
    "            if s in d:\n",
    "                d[s].next = head.next\n",
    "                return self.removeZeroSumSublists(l.next)\n",
    "            else:\n",
    "                d[s] = head\n",
    "                head = head.next\n",
    "        return l.next\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeZeroSumSublists(self, head: ListNode) -> ListNode:\n",
    "        l = ListNode(0)\n",
    "        l.next = head\n",
    "        d = {0:l}\n",
    "        s = 0\n",
    "        while head:\n",
    "            s+=head.val\n",
    "            if s in d:\n",
    "                d[s].next = head.next\n",
    "                return self.removeZeroSumSublists(l.next)\n",
    "            else:\n",
    "                d[s] = head\n",
    "                head = head.next\n",
    "        return l.next\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeZeroSumSublists(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        dic = {}\n",
    "        cur = head\n",
    "        s = 0\n",
    "        while cur:\n",
    "            s += cur.val\n",
    "            dic[s]  = cur\n",
    "            cur = cur.next\n",
    "        res = ListNode()\n",
    "        s = 0\n",
    "        if 0 in dic:\n",
    "            head = dic[0].next\n",
    "        res.next = head\n",
    "        while head:\n",
    "            s += head.val\n",
    "            head.next = dic[s].next\n",
    "            head = head.next\n",
    "        return res.next\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeZeroSumSublists(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        p = head\n",
    "        prefix = 0\n",
    "        pres = {}\n",
    "        pres[0] = ret = ListNode(0, head)\n",
    "\n",
    "        while p:\n",
    "            prefix += p.val\n",
    "            pres[prefix] = p\n",
    "            p = p.next\n",
    "\n",
    "        p = ret\n",
    "        prefix = 0\n",
    "\n",
    "        while p:\n",
    "            prefix += p.val\n",
    "            p.next = pres[prefix].next\n",
    "            p = p.next\n",
    "        return ret.next\n",
    "            \n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeZeroSumSublists(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        dummy = ListNode(0)\n",
    "        dummy.next = head\n",
    "        while True:\n",
    "            p = dummy\n",
    "            #print(p)\n",
    "            dic = {}\n",
    "            total = 0\n",
    "            con = False\n",
    "            while p:\n",
    "                total += p.val\n",
    "                if total not in dic:\n",
    "                    dic[total] = p\n",
    "                else:\n",
    "                    #print(total)\n",
    "                    dic[total].next = p.next\n",
    "                    con = True\n",
    "                    break\n",
    "                p = p.next\n",
    "            if con:\n",
    "                continue\n",
    "            else:\n",
    "                break\n",
    "        \n",
    "        return dummy.next\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeZeroSumSublists(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        root = ListNode(0, head)\n",
    "        d = {}\n",
    "        pre = root\n",
    "        p = root.next\n",
    "        s = 0\n",
    "        while p:\n",
    "            s += p.val\n",
    "            if s == 0:\n",
    "                root.next = p.next\n",
    "                if root is None:\n",
    "                    break\n",
    "                pre = root\n",
    "                p = root.next\n",
    "                continue\n",
    "            if s not in d:\n",
    "                d[s] = p\n",
    "                p = p.next\n",
    "                pre = pre.next\n",
    "            else:\n",
    "                d[s].next = p.next\n",
    "                pre = root\n",
    "                p = root.next\n",
    "                d = {}\n",
    "                s = 0\n",
    "        return root.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeZeroSumSublists(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        virtual = ListNode(next = head)\n",
    "        temp1 = head\n",
    "        prefix_sum = 0\n",
    "        prefix_sum_dict = {0:virtual}\n",
    "        prefix_sum_dict2 = {virtual:0}\n",
    "        while temp1 != None:\n",
    "            prefix_sum += temp1.val\n",
    "            if prefix_sum_dict.get(prefix_sum) == None:\n",
    "                prefix_sum_dict[prefix_sum] = temp1\n",
    "                prefix_sum_dict2[temp1] = prefix_sum\n",
    "            else:\n",
    "                prefix_sum_dict2[temp1] = prefix_sum\n",
    "                node = prefix_sum_dict.get(prefix_sum)\n",
    "                del_node = node.next\n",
    "                while del_node != temp1:\n",
    "                    prefix_sum_dict[prefix_sum_dict2[del_node]] = None\n",
    "                    del_node = del_node.next\n",
    "                node.next = temp1.next\n",
    "            temp1 = temp1.next\n",
    "        return virtual.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeZeroSumSublists(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        if head is None:\n",
    "            return None\n",
    "        prefix = {}\n",
    "        head_ = ListNode(next=head)\n",
    "        prefix[0] = head_\n",
    "        total = 0\n",
    "        p = head\n",
    "        while p is not None:\n",
    "            total += p.val\n",
    "            if total in prefix:\n",
    "                node = prefix[total]\n",
    "                curr = 0\n",
    "                p1 = node.next\n",
    "                while p1 != p:\n",
    "                    curr += p1.val\n",
    "                    del prefix[total + curr]\n",
    "                    p1 = p1.next\n",
    "                node.next = p.next\n",
    "                \n",
    "            else:\n",
    "                prefix[total] = p\n",
    "            p = p.next\n",
    "            \n",
    "        return  head_.next\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeZeroSumSublists(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        ### 之所以在head前面绑定一个空，是因为 万一head整个被删了呢？\n",
    "        res = ListNode(next = head)\n",
    "        \n",
    "        ### 这里必须从 0开始，而不是从head 开始，不然就会在 head = [1,-1] 时出错 ###\n",
    "        sum_dic = {}\n",
    "        cur = res # cur = head\n",
    "        cur_sum = 0\n",
    "        while cur:\n",
    "            cur_sum += cur.val\n",
    "            sum_dic[cur_sum] = cur\n",
    "            cur = cur.next\n",
    "            \n",
    "        cur = res # cur = head\n",
    "        cur_sum = 0\n",
    "        while cur:\n",
    "            cur_sum += cur.val\n",
    "            # 出现两个 前缀和一样的点， 此时 cur 就是 前一个， sum_dic[cur_sum] 就是后一个\n",
    "            # 如果其实这两个就是同一个，也就是 相同前缀和 没出现两次，那么也不影响\n",
    "            cur.next = sum_dic[cur_sum].next\n",
    "            cur = cur.next\n",
    "            \n",
    "        return(res.next)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeZeroSumSublists(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        # head = ListNode(next = head)\n",
    "        valis = []\n",
    "        nodelis = []\n",
    "        \n",
    "        while head:\n",
    "\n",
    "            node = head\n",
    "            head = head.next\n",
    "            node.next = None\n",
    "            val = node.val\n",
    "            # print(\"val:\", val)\n",
    "            if val != 0:\n",
    "                s = val\n",
    "                flag = 1\n",
    "                for i in range(len(nodelis)-1,-1,-1):\n",
    "                    s += valis[i]\n",
    "                    # print(s)\n",
    "                    if s == 0:\n",
    "                        valis = valis[0:i]\n",
    "                        nodelis = nodelis[0:i]\n",
    "                        flag = 0\n",
    "                        break\n",
    "                if flag:\n",
    "                    valis.append(val)\n",
    "                    nodelis.append(node)\n",
    "\n",
    "        ans = ListNode()\n",
    "        ans0 = ans\n",
    "        for node in nodelis:\n",
    "            # print(node)\n",
    "            ans.next = node\n",
    "            ans = ans.next\n",
    "        \n",
    "        return ans0.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeZeroSumSublists(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        dummy = ListNode()\n",
    "        dummy.next = head\n",
    "        ret_head = dummy\n",
    "        if head.val == 0:\n",
    "            ret_head.next = head.next\n",
    "        l, r = head, head.next\n",
    "        s = l.val\n",
    "        while l.next:\n",
    "            if s == 0:\n",
    "                ret_head.next = r\n",
    "                if r:\n",
    "                    s = r.val\n",
    "                # ret_head = r\n",
    "            else:\n",
    "                if r:\n",
    "                    s += r.val\n",
    "            if r:\n",
    "                r = r.next\n",
    "            else:\n",
    "                ret_head = l\n",
    "                l = l.next\n",
    "                r = l.next\n",
    "                s = l.val\n",
    "                if s==0:\n",
    "                    ret_head.next = l.next\n",
    "        return dummy.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeZeroSumSublists(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        l = []\n",
    "        c = dict()\n",
    "        s = 0\n",
    "        res = ListNode(next=head)\n",
    "        ptr = res\n",
    "        while ptr:\n",
    "            s += ptr.val\n",
    "            if s in c:\n",
    "                c[s].next = ptr.next\n",
    "                while l[-1] != s:\n",
    "                    del c[l.pop()]\n",
    "            else:\n",
    "                l.append(s)\n",
    "                c[s] = ptr\n",
    "            ptr = ptr.next\n",
    "        return res.next\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeZeroSumSublists(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        while True:\n",
    "            d = {0: None}\n",
    "            p = head\n",
    "            s = 0\n",
    "            while p != None:\n",
    "                s += p.val\n",
    "                if s in d:\n",
    "                    t = d[s]\n",
    "                    if t == None:\n",
    "                        head = p.next\n",
    "                    else:\n",
    "                        t.next = p.next\n",
    "                    break\n",
    "                else:\n",
    "                    d[s] = p\n",
    "                p = p.next\n",
    "            if p == None:\n",
    "                return head\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeZeroSumSublists(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        # 前缀和 + 哈希表 + 一次遍历\n",
    "        pre_sum_dict = {}\n",
    "        pre_sum = 0\n",
    "        # 定义哑结点\n",
    "        dummy = ListNode(next=head)\n",
    "        node = dummy\n",
    "\n",
    "        while node:\n",
    "            pre_sum += node.val\n",
    "            if pre_sum in pre_sum_dict:\n",
    "                # 删除哈希表里记录\n",
    "                remove_node = pre_sum_dict[pre_sum].next\n",
    "                remove_sum = pre_sum\n",
    "                while remove_node != node:\n",
    "                    remove_sum += remove_node.val\n",
    "                    pre_sum_dict.pop(remove_sum)\n",
    "                    remove_node = remove_node.next\n",
    "                # 删除中间相加=0的节点\n",
    "                # 此时哈希表里记录的是上一个前缀和的节点\n",
    "                pre_sum_dict[pre_sum].next = node.next\n",
    "            else:\n",
    "                pre_sum_dict[pre_sum] = node\n",
    "            node = node.next\n",
    "        return dummy.next\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeZeroSumSublists(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        seen = {}\n",
    "        seen[0] = dummy = ListNode(0)\n",
    "        dummy.next = head\n",
    "        prefix = 0\n",
    "        while head:\n",
    "            prefix += head.val\n",
    "            seen[prefix] = head \n",
    "            head = head.next\n",
    "        head = dummy\n",
    "        prefix = 0\n",
    "        while head:\n",
    "            prefix += head.val\n",
    "            head.next = seen[prefix].next\n",
    "            head = head.next\n",
    "        return dummy.next\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeZeroSumSublists(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        pre = ListNode(0,next=head)\n",
    "        cur = pre\n",
    "        pre_sum = 0\n",
    "        dic = {}\n",
    "        while cur:\n",
    "            \n",
    "            pre_sum += cur.val\n",
    "            dic[pre_sum] = cur\n",
    "            cur = cur.next\n",
    "\n",
    "        cur = pre\n",
    "        pre_sum = 0\n",
    "\n",
    "        while cur:\n",
    "            pre_sum += cur.val\n",
    "            #if dic[pre_sum]:\n",
    "            cur.next = dic[pre_sum].next\n",
    "            cur = cur.next    \n",
    "\n",
    "        return pre.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeZeroSumSublists(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        if not head:\n",
    "            return None\n",
    "        \n",
    "        if not head.next:\n",
    "            return head if head.val != 0 else None\n",
    "        \n",
    "        dummy = ListNode(-1001, head)\n",
    "        preCurr = dummy\n",
    "        curr = head\n",
    "\n",
    "        while curr:\n",
    "            sumVal = 0\n",
    "            found = False\n",
    "            tmpPtr = curr\n",
    "            while tmpPtr:\n",
    "                sumVal += tmpPtr.val\n",
    "                if sumVal == 0:\n",
    "                    found = True\n",
    "                    break\n",
    "                tmpPtr = tmpPtr.next\n",
    "            \n",
    "            if found:\n",
    "                preCurr.next = tmpPtr.next\n",
    "                curr = tmpPtr.next\n",
    "            else:\n",
    "                preCurr = curr\n",
    "                curr = curr.next\n",
    "        \n",
    "        return dummy.next\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeZeroSumSublists(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        prefix = 0\n",
    "        seen = {}\n",
    "        seen[0] = dummy = ListNode(0)\n",
    "        dummy.next = head\n",
    "        while head:\n",
    "            prefix += head.val\n",
    "            seen[prefix] = head\n",
    "            head = head.next\n",
    "        head = dummy\n",
    "        prefix = 0\n",
    "        while head:\n",
    "            prefix += head.val\n",
    "            head.next = seen[prefix].next\n",
    "            head = head.next\n",
    "        return dummy.next\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeZeroSumSublists(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        d = {}\n",
    "        head = ListNode(0, head)\n",
    "        node = head\n",
    "        current = 0\n",
    "        while node:\n",
    "            current += node.val\n",
    "            if current in d:\n",
    "                pre_node = d[current]\n",
    "                node_ = head\n",
    "                while node_:\n",
    "                    if node_ == pre_node:\n",
    "                        break\n",
    "                    node_ = node_.next\n",
    "                node_.next = node.next\n",
    "                node = head\n",
    "                current = 0\n",
    "                d.clear()\n",
    "            d[current] = node\n",
    "            node = node.next\n",
    "        return head.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeZeroSumSublists(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        dummynode = ListNode()\n",
    "        dummynode.next = head\n",
    "        presum = {}\n",
    "        cur = dummynode\n",
    "        pre = 0\n",
    "        while cur:\n",
    "            pre += cur.val\n",
    "            presum[pre] = cur\n",
    "            cur = cur.next\n",
    "        # print(presum)\n",
    "        pre = 0\n",
    "        cur = dummynode\n",
    "        while cur:\n",
    "            pre += cur.val\n",
    "            # print(cur.val, pre)\n",
    "            cur.next = presum[pre].next\n",
    "            cur = cur.next\n",
    "        return dummynode.next\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeZeroSumSublists(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        self.flag = 1\n",
    "        def f(head):\n",
    "            self.flag = 0\n",
    "            cur = ListNode(0,head)\n",
    "            dummy = ListNode(0,ListNode(0,head))\n",
    "            prefixsum = [0]\n",
    "            cnt = 0\n",
    "            st = {0:0}\n",
    "            while cur and cur.next:\n",
    "                if prefixsum[-1] + cur.next.val in prefixsum:\n",
    "                    self.flag = 1\n",
    "                    pre = ListNode(0,ListNode(0,head))\n",
    "                    dummy = pre\n",
    "                    cnt1 = -1\n",
    "                    while cnt1 != st[prefixsum[-1] + cur.next.val]:\n",
    "                        pre = pre.next\n",
    "                        cnt1 += 1\n",
    "                    pre.next = cur.next.next\n",
    "                    break\n",
    "                cnt += 1\n",
    "                prefixsum.append(prefixsum[-1] + cur.next.val)\n",
    "                st[prefixsum[-1]] = cnt\n",
    "                cur = cur.next\n",
    "            return dummy.next.next\n",
    "        \n",
    "        while self.flag == 1:\n",
    "            head = f(head)\n",
    "\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeZeroSumSublists(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        prefix = 0\n",
    "        seen = dict()\n",
    "        seen[0] = dummy_node = ListNode(0)\n",
    "        dummy_node.next = head\n",
    "        while head:\n",
    "            prefix += head.val\n",
    "            seen[prefix] = head\n",
    "            head = head.next\n",
    "        \n",
    "        prefix = 0\n",
    "        head = dummy_node\n",
    "        while head:\n",
    "            prefix += head.val\n",
    "            head.next = seen[prefix].next\n",
    "            head = head.next\n",
    "        return dummy_node.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeZeroSumSublists(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        prefix = 0\n",
    "        seen = {}\n",
    "        seen[0] = dummy = ListNode(0)\n",
    "        dummy.next = head\n",
    "        while head:\n",
    "            prefix += head.val\n",
    "            seen[prefix] = head\n",
    "            head = head.next\n",
    "        head = dummy\n",
    "        prefix = 0\n",
    "        while head:\n",
    "            prefix +=head.val\n",
    "            head.next = seen[prefix].next\n",
    "            head = head.next\n",
    "        return dummy.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeZeroSumSublists(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        prefix = 0\n",
    "        seen = {}\n",
    "        seen[0] = dummy = ListNode(0)\n",
    "        dummy.next = head\n",
    "        while head:\n",
    "            prefix += head.val\n",
    "            seen[prefix] = head\n",
    "            head = head.next\n",
    "        head = dummy\n",
    "        prefix = 0\n",
    "        while head:\n",
    "            prefix += head.val\n",
    "            head.next = seen[prefix].next\n",
    "            head = head.next\n",
    "        return dummy.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeZeroSumSublists(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        dummy=ListNode()\n",
    "        dummy.next=head\n",
    "        changed=False\n",
    "        while True:\n",
    "            pre_sum=0\n",
    "            pre_map={0:dummy}\n",
    "            head=dummy.next\n",
    "            while head:\n",
    "                pre_sum+=head.val\n",
    "                if pre_sum not in pre_map:\n",
    "                    pre_map[pre_sum]=head\n",
    "                else:\n",
    "                    pre_map[pre_sum].next=head.next\n",
    "                    changed=True\n",
    "                    break\n",
    "                head=head.next\n",
    "            if not changed:\n",
    "                break\n",
    "            changed=False\n",
    "        return dummy.next "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeZeroSumSublists(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        prefix = 0\n",
    "        seen = {}\n",
    "        seen[0] = dummy = ListNode(0)\n",
    "        dummy.next = head\n",
    "        while head:\n",
    "            prefix += head.val\n",
    "            seen[prefix] = head\n",
    "            head = head.next\n",
    "        head = dummy\n",
    "        prefix = 0\n",
    "        while head:\n",
    "            prefix += head.val\n",
    "            head.next = seen[prefix].next\n",
    "            head = head.next\n",
    "        return dummy.next\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeZeroSumSublists(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        prefix=0\n",
    "        dummy=ListNode(0)\n",
    "        dummy.next=head\n",
    "        d={}\n",
    "        d[prefix]=dummy\n",
    "        while head:\n",
    "            prefix+= head.val\n",
    "            d[prefix]=head\n",
    "            head=head.next\n",
    "        head=dummy\n",
    "        prefix=0\n",
    "        while head:\n",
    "            prefix+=head.val\n",
    "            head.next=d[prefix].next\n",
    "            head=head.next\n",
    "        return dummy.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeZeroSumSublists(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        sums = {}\n",
    "        tmp = head\n",
    "        cur = 0\n",
    "        sums[0] = dummy = ListNode(0)\n",
    "        dummy.next =  head\n",
    "        while tmp:\n",
    "            cur += tmp.val\n",
    "            sums[cur] = tmp\n",
    "            tmp = tmp.next\n",
    "        cur = 0\n",
    "        head = dummy\n",
    "        while head:\n",
    "            cur += head.val\n",
    "            head.next = sums[cur].next\n",
    "            head = head.next\n",
    "        return dummy.next\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeZeroSumSublists(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        prefix = 0\n",
    "        seen = {}\n",
    "        seen[0] = dummy = ListNode(0)\n",
    "        dummy.next = head\n",
    "        while head:\n",
    "            prefix += head.val\n",
    "            seen[prefix] = head\n",
    "            head = head.next\n",
    "        head = dummy\n",
    "        prefix = 0\n",
    "        while head:\n",
    "            prefix += head.val\n",
    "            head.next = seen[prefix].next\n",
    "            head = head.next\n",
    "        return dummy.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeZeroSumSublists(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        pre_head = ListNode(next=head)\n",
    "        acc = {}\n",
    "\n",
    "        cur = pre_head\n",
    "        sum_val = 0\n",
    "        while cur:\n",
    "            sum_val += cur.val\n",
    "            acc[sum_val] = cur\n",
    "            cur = cur.next\n",
    "\n",
    "        cur = pre_head\n",
    "        sum_val = 0\n",
    "        while cur:\n",
    "            sum_val += cur.val\n",
    "            next_node = acc.get(sum_val, None)\n",
    "            if next_node != cur:\n",
    "                cur.next = next_node.next\n",
    "            cur = cur.next\n",
    "        return pre_head.next\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeZeroSumSublists(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        prefix = 0\n",
    "        seen = {}\n",
    "        seen[0] = dummy = ListNode(0)\n",
    "        dummy.next = head\n",
    "        while head:\n",
    "            prefix += head.val\n",
    "            seen[prefix] = head\n",
    "            head = head.next\n",
    "        head, prefix = dummy, 0\n",
    "        while head:\n",
    "            prefix += head.val\n",
    "            head.next = seen[prefix].next\n",
    "            head = head.next\n",
    "        return dummy.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeZeroSumSublists(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        mp = {}\n",
    "        ptr = ListNode(0)\n",
    "        ans = ptr\n",
    "        ptr.next = head\n",
    "        pre = 0\n",
    "        while ptr:\n",
    "            pre += ptr.val\n",
    "            mp[pre] = ptr\n",
    "            ptr = ptr.next\n",
    "        ptr = ans\n",
    "        pre = 0\n",
    "        while ptr:\n",
    "            pre += ptr.val\n",
    "            if pre not in mp:\n",
    "                ptr = ptr.next\n",
    "            else:\n",
    "                ptr.next = mp[pre].next\n",
    "                ptr = ptr.next\n",
    "        return ans.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeZeroSumSublists(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        prefix = 0\n",
    "        seen = {}\n",
    "        seen[0] = dummy = ListNode(0)\n",
    "        dummy.next = head\n",
    "        while head:\n",
    "            prefix += head.val\n",
    "            seen[prefix] = head\n",
    "            head = head.next\n",
    "        head = dummy\n",
    "        prefix = 0\n",
    "        while head:\n",
    "            prefix += head.val\n",
    "            head.next = seen[prefix].next\n",
    "            head = head.next\n",
    "        return dummy.next\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeZeroSumSublists(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        dummy = ListNode(next=head)\n",
    "        last = {}\n",
    "        s, cur = 0, dummy\n",
    "        while cur:\n",
    "            s += cur.val\n",
    "            last[s] = cur\n",
    "            cur = cur.next\n",
    "        s, cur = 0, dummy\n",
    "        while cur:\n",
    "            s += cur.val\n",
    "            cur.next = last[s].next\n",
    "            cur = cur.next\n",
    "        return dummy.next\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeZeroSumSublists(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        dummy = ListNode(next = head)\n",
    "        s , cur = 0 , dummy\n",
    "        last = {}\n",
    "        while cur:\n",
    "            s += cur.val\n",
    "            last[s] = cur\n",
    "            cur = cur.next\n",
    "        s , cur = 0 , dummy\n",
    "        while cur:\n",
    "            s += cur.val\n",
    "            cur.next = last[s].next\n",
    "            cur = cur.next\n",
    "        return dummy.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeZeroSumSublists(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        dummy = ListNode(next=head)\n",
    "        last = {}\n",
    "        s, cur = 0, dummy\n",
    "        while cur:\n",
    "            s += cur.val\n",
    "            last[s] = cur\n",
    "            cur = cur.next\n",
    "        s, cur = 0, dummy\n",
    "        while cur:\n",
    "            s += cur.val\n",
    "            cur.next = last[s].next\n",
    "            cur = cur.next\n",
    "        return dummy.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeZeroSumSublists(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        prefix = 0\n",
    "        seen = {}\n",
    "        seen[0] = dummy = ListNode(0)\n",
    "        dummy.next = head\n",
    "        while head:\n",
    "            prefix += head.val\n",
    "            seen[prefix] = head\n",
    "            head = head.next\n",
    "        head = dummy\n",
    "        prefix = 0\n",
    "        while head:\n",
    "            prefix += head.val\n",
    "            head.next = seen[prefix].next\n",
    "            head = head.next\n",
    "        return dummy.next\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeZeroSumSublists(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        prefix = 0\n",
    "        seen = {}\n",
    "        seen[0] = dummy = ListNode(0)\n",
    "        dummy.next = head\n",
    "        while head:\n",
    "            prefix += head.val\n",
    "            seen[prefix] = head\n",
    "            head = head.next\n",
    "        head = dummy\n",
    "        prefix = 0\n",
    "        while head:\n",
    "            prefix += head.val\n",
    "            head.next = seen[prefix].next\n",
    "            head = head.next\n",
    "        return dummy.next\n",
    "        \n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeZeroSumSublists(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        stack={}\n",
    "        heads=head\n",
    "        sums=0\n",
    "        mid=mid2=ListNode(0)\n",
    "        mid.next=head\n",
    "        stack[0]=mid\n",
    "        while heads:\n",
    "            sums+=heads.val\n",
    "            stack[sums]=heads\n",
    "            heads=heads.next\n",
    "        \n",
    "        sums=0\n",
    "        while mid:\n",
    "            sums+=mid.val\n",
    "            mid.next=stack[sums].next\n",
    "            mid=mid.next\n",
    "            \n",
    "        return mid2.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeZeroSumSublists(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        pre_sum_dict = {}       # 哈希表记录前缀和和节点映射\n",
    "        pre_sum = 0             # 前缀和\n",
    "        dummy = ListNode(0) # 伪节点，接在头节点之前\n",
    "        dummy.next =head\n",
    "        node = head            # 从伪节点开始遍历\n",
    "\n",
    "        # 一次遍历，记录每个前缀和和最后出现的节点\n",
    "        while node is not None:\n",
    "            pre_sum += node.val\n",
    "            pre_sum_dict[pre_sum] = node\n",
    "            node = node.next\n",
    "        \n",
    "        # 二次遍历\n",
    "        node = dummy\n",
    "        pre_sum = 0\n",
    "        while node is not None:\n",
    "            pre_sum += node.val\n",
    "            if pre_sum in pre_sum_dict:\n",
    "                # 当前前缀和存在，当前节点的next指向记录节点的next；即删除当前节点的next到记录节点这个子链表\n",
    "                node.next = pre_sum_dict[pre_sum].next\n",
    "            node = node.next\n",
    "        return dummy.next\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeZeroSumSublists(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        prefix = 0\n",
    "        seen = {}\n",
    "        dummyhead = ListNode(0, head)\n",
    "        seen[0] = dummyhead\n",
    "        while head:\n",
    "            prefix += head.val\n",
    "            seen[prefix] = head\n",
    "            head = head.next\n",
    "        head = dummyhead\n",
    "        prefix = 0\n",
    "        while head:\n",
    "            prefix += head.val\n",
    "            head.next = seen[prefix].next\n",
    "            head = head.next\n",
    "        return dummyhead.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeZeroSumSublists(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        dummy = ListNode(next=head)\n",
    "        node, pre_sum = dummy, 0\n",
    "        prefix = collections.defaultdict(ListNode)\n",
    "        while node:\n",
    "            pre_sum += node.val\n",
    "            prefix[pre_sum] = node\n",
    "            node = node.next\n",
    "\n",
    "        node, pre_sum = dummy, 0\n",
    "        while node:\n",
    "            pre_sum += node.val\n",
    "            node.next = prefix[pre_sum].next\n",
    "            node = node.next\n",
    "        \n",
    "        return dummy.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeZeroSumSublists(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        dummy = ListNode()\n",
    "        cur = head\n",
    "        exists = {0: dummy} \n",
    "        dummy.next = head\n",
    "        prefix = 0\n",
    "        while cur:\n",
    "            prefix += cur.val\n",
    "            exists[prefix] = cur\n",
    "            cur = cur.next\n",
    "\n",
    "        prefix = 0\n",
    "        cur = dummy\n",
    "        while cur:\n",
    "            prefix += cur.val\n",
    "            cur.next = exists[prefix].next\n",
    "            cur = cur.next\n",
    "        return dummy.next        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeZeroSumSublists(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        dummy = ListNode(next=head)\n",
    "        last = {}\n",
    "        s, cur = 0, dummy\n",
    "        while cur:\n",
    "            s += cur.val\n",
    "            last[s] = cur\n",
    "            cur = cur.next\n",
    "        s, cur = 0, dummy\n",
    "        while cur:\n",
    "            s += cur.val\n",
    "            cur.next = last[s].next\n",
    "            cur = cur.next\n",
    "        return dummy.next\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeZeroSumSublists(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        dummy = ListNode(next=head)\n",
    "        last = {}\n",
    "        s, cur = 0, dummy\n",
    "        while cur:\n",
    "            s+=cur.val\n",
    "            last[s] = cur\n",
    "            cur = cur.next\n",
    "        s, cur = 0, dummy\n",
    "        while cur:\n",
    "            s+=cur.val\n",
    "            cur.next = last[s].next\n",
    "            cur = cur.next\n",
    "        return dummy.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeZeroSumSublists(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        dummy = ListNode()\n",
    "        dummy.next = head\n",
    "        d = {0:dummy}\n",
    "        s = 0\n",
    "        while head:\n",
    "            s += head.val\n",
    "            d[s] = head\n",
    "            head = head.next\n",
    "        head = dummy\n",
    "        s = 0\n",
    "        while head:\n",
    "            s += head.val\n",
    "            head.next = d[s].next\n",
    "            head = head.next\n",
    "        return dummy.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeZeroSumSublists(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "\n",
    "\n",
    "\n",
    "        dummy = ListNode()\n",
    "        cur = head\n",
    "        exists = {0: dummy} \n",
    "        dummy.next = head\n",
    "        prefix = 0\n",
    "        while cur:\n",
    "            prefix += cur.val\n",
    "            exists[prefix] = cur\n",
    "            cur = cur.next\n",
    "\n",
    "        prefix = 0\n",
    "        cur = dummy\n",
    "        while cur:\n",
    "            prefix += cur.val\n",
    "            cur.next = exists[prefix].next\n",
    "            cur = cur.next\n",
    "        return dummy.next        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeZeroSumSublists(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        dummy = ListNode()\n",
    "        dummy.next = head\n",
    "        d,s = {0:dummy},0\n",
    "        while head:\n",
    "            s += head.val\n",
    "            d[s] = head\n",
    "            head = head.next\n",
    "        s = 0\n",
    "        head = dummy\n",
    "        while head:\n",
    "            s += head.val\n",
    "            head.next = d[s].next\n",
    "            head = head.next\n",
    "        return dummy.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeZeroSumSublists(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        pre_sum = 0\n",
    "        dummy = ListNode(val=0,next=head)\n",
    "        dic = {}\n",
    "        p0 = dummy\n",
    "        while p0:\n",
    "            pre_sum += p0.val\n",
    "            dic[pre_sum] = p0\n",
    "            p0 = p0.next\n",
    "        p0 = dummy\n",
    "        pre_sum = 0\n",
    "        while p0:\n",
    "            pre_sum += p0.val\n",
    "            p0.next = dic[pre_sum].next\n",
    "            p0 = p0.next\n",
    "        return dummy.next\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeZeroSumSublists(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        prefix = 0\n",
    "        seen = {}\n",
    "        seen[0] = dummy = ListNode(0)\n",
    "        dummy.next = head\n",
    "        while head:\n",
    "            prefix += head.val\n",
    "            seen[prefix] = head\n",
    "            head = head.next\n",
    "        prefix = 0\n",
    "        head = dummy\n",
    "        while head:\n",
    "            prefix += head.val\n",
    "            head.next = seen[prefix].next\n",
    "            head = head.next\n",
    "        return dummy.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeZeroSumSublists(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        result = {}\n",
    "        dummy = ListNode()\n",
    "        dummy.next = head\n",
    "        cur = dummy\n",
    "        sr = 0\n",
    "        while cur:\n",
    "            sr = sr+cur.val\n",
    "            result[sr] = cur\n",
    "            cur = cur.next\n",
    "\n",
    "        cur = dummy\n",
    "        sr = 0\n",
    "        while cur:\n",
    "            sr = sr+cur.val\n",
    "            if sr in result:\n",
    "                cur.next = result[sr].next\n",
    "            cur = cur.next\n",
    "        return dummy.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeZeroSumSublists(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        if not head.next:\n",
    "            if head.val == 0:\n",
    "                return None \n",
    "            return head \n",
    "\n",
    "        dummy = ListNode()\n",
    "        dummy.next = head \n",
    "        m1 = dict()\n",
    "        pre = 0\n",
    "        m1[0] = dummy\n",
    "\n",
    "        p = head \n",
    "        while p:\n",
    "            pre += p.val\n",
    "            m1[pre] = p \n",
    "            p = p.next\n",
    "\n",
    "        pre = 0\n",
    "        p = dummy\n",
    "        while p:\n",
    "            pre += p.val\n",
    "            if pre in m1:\n",
    "                node = m1[pre]\n",
    "                p.next = node.next\n",
    "            p = p.next\n",
    "\n",
    "        return dummy.next\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeZeroSumSublists(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        mp = {}\n",
    "        ptr = ListNode(0)\n",
    "        ans = ptr\n",
    "        ptr.next = head\n",
    "        pre = 0\n",
    "        while ptr:\n",
    "            pre += ptr.val\n",
    "            mp[pre] = ptr\n",
    "            ptr = ptr.next\n",
    "        ptr = ans\n",
    "        pre = 0\n",
    "        while ptr:\n",
    "            pre += ptr.val\n",
    "            if pre not in mp:\n",
    "                ptr = ptr.next\n",
    "            else:\n",
    "                ptr.next = mp[pre].next\n",
    "                ptr = ptr.next\n",
    "        return ans.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeZeroSumSublists(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        dummy = ListNode(next=head)\n",
    "        last={}\n",
    "        s,cur=0,dummy\n",
    "        while cur:\n",
    "            s+=cur.val\n",
    "            last[s]=cur\n",
    "            cur=cur.next\n",
    "        s,cur=0,dummy\n",
    "        while cur:\n",
    "            s+=cur.val\n",
    "            cur.next=last[s].next\n",
    "            cur=cur.next\n",
    "        return dummy.next\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "from typing import Optional\n",
    "\n",
    "\n",
    "class ListNode:\n",
    "    def __init__(self, val=0, next=None):\n",
    "        self.val = val\n",
    "        self.next = next\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def removeZeroSumSublists(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        \"\"\"\n",
    "        两次遍历\n",
    "        1. 第一次遍历:记录前缀和\n",
    "        2. 第二次遍历:删除相应的节点\n",
    "        \"\"\"\n",
    "        dummy = ListNode(0, head)\n",
    "        last = dict()\n",
    "\n",
    "        s = 0\n",
    "        pre = dummy\n",
    "        while pre:\n",
    "            s += pre.val\n",
    "            last[s] = pre\n",
    "            pre = pre.next\n",
    "\n",
    "        s = 0\n",
    "        pre = dummy\n",
    "        while pre:\n",
    "            s += pre.val\n",
    "            pre.next = last[s].next\n",
    "            pre = pre.next\n",
    "\n",
    "        return dummy.next\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeZeroSumSublists(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        mp = {}\n",
    "        ptr = ListNode(0)\n",
    "        ans = ptr\n",
    "        ptr.next = head\n",
    "        pre = 0\n",
    "        while ptr:\n",
    "            pre += ptr.val\n",
    "            mp[pre] = ptr\n",
    "            ptr = ptr.next\n",
    "        ptr, pre = ans, 0\n",
    "        while ptr:\n",
    "            pre += ptr.val\n",
    "            if pre not in mp:\n",
    "                ptr = ptr.next\n",
    "            else:\n",
    "                ptr.next = mp[pre].next\n",
    "                ptr = ptr.next\n",
    "        return ans.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeZeroSumSublists(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        g = []\n",
    "        while head:\n",
    "            if head.val != 0:\n",
    "                g.append(head.val)\n",
    "            head = head.next\n",
    "        while True:\n",
    "            vis = dict()\n",
    "            vis[0] = -1\n",
    "            tot = 0\n",
    "            l = len(g)\n",
    "            for i, x in enumerate(g):\n",
    "                tot += x\n",
    "                if tot in vis:\n",
    "                    prv = vis[tot]\n",
    "                    if prv == -1:\n",
    "                        g = g[i+1:]\n",
    "                    else:\n",
    "                        g = g[:prv+1] + g[i+1:]\n",
    "                    break\n",
    "                else:\n",
    "                    vis[tot] = i\n",
    "            if l == len(g):\n",
    "                break\n",
    "        dummy = tmp = ListNode()\n",
    "        for x in g:\n",
    "            tmp.next = ListNode(x)\n",
    "            tmp = tmp.next\n",
    "        return dummy.next\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeZeroSumSublists(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        cnt = defaultdict(ListNode)\n",
    "        dummy = ListNode(-1, head)\n",
    "        cur = dummy\n",
    "        s = 0\n",
    "        while cur:\n",
    "            s += cur.val\n",
    "            cnt[s] = cur\n",
    "            cur = cur.next\n",
    "        s = 0\n",
    "        cur = dummy\n",
    "        while cur:\n",
    "            s += cur.val\n",
    "            cur.next = cnt[s].next\n",
    "            cur = cur.next\n",
    "        return dummy.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeZeroSumSublists(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        if not head:\n",
    "            return \n",
    "\n",
    "        total = 0\n",
    "        cur = head \n",
    "        while cur:\n",
    "            total += cur.val \n",
    "            if total == 0:\n",
    "                return self.removeZeroSumSublists(cur.next)\n",
    "            cur = cur.next \n",
    "        head.next = self.removeZeroSumSublists(head.next)\n",
    "        return head \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeZeroSumSublists(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        newHead = ListNode(0, next=head)\n",
    "        seen = {}\n",
    "        seen[0] = newHead\n",
    "        prefix = 0\n",
    "        while head:\n",
    "            prefix += head.val\n",
    "            seen[prefix] = head\n",
    "            head = head.next\n",
    "        \n",
    "        head = newHead\n",
    "        prefix = 0\n",
    "        while head:\n",
    "            prefix += head.val\n",
    "            head.next = seen[prefix].next\n",
    "            head = head.next\n",
    "        return newHead.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeZeroSumSublists(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        ll = []\n",
    "        while head:\n",
    "            ll.append(head.val)\n",
    "            head = head.next\n",
    "        stack = [0]\n",
    "\n",
    "        m = 0\n",
    "        i = 0\n",
    "        while i < len(ll):\n",
    "            #print(i, ll, stack, m)\n",
    "            if ll[i] + m in stack:\n",
    "                a = stack.index(ll[i] + m) - 1\n",
    "                stack = stack[: a + 2]\n",
    "                m += ll[i]\n",
    "                ll = ll[: a + 1] + ll[i + 1:]\n",
    "                i = a + 1\n",
    "            else: \n",
    "                m += ll[i]\n",
    "                stack.append(m)\n",
    "                i += 1\n",
    "        #print(ll)\n",
    "        if not ll:\n",
    "            return None\n",
    "        p = ListNode(ll[0])            # 将头节点赋给p \n",
    "        ll.pop(0)\n",
    "        p1 = p\n",
    "        for item in ll: \n",
    "            p1.next = ListNode(item)  # 将下一个节点添加在当前节点（p）之后\n",
    "            p1 = p1.next\n",
    "        #print(p)\n",
    "\n",
    "\n",
    "        return p\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeZeroSumSublists(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "      stack = []\n",
    "      pos = head\n",
    "      cur_sum = 0\n",
    "\n",
    "      while pos:\n",
    "        if pos.val == 0:\n",
    "          pos = pos.next\n",
    "          continue\n",
    "        else:\n",
    "          popped = []\n",
    "          cur_sum = pos.val\n",
    "          while stack and cur_sum != 0:\n",
    "            cur_sum += stack[-1].val\n",
    "            popped.append(stack.pop())\n",
    "\n",
    "          if cur_sum != 0:\n",
    "            while popped:\n",
    "              stack.append(popped.pop())\n",
    "            stack.append(pos)\n",
    "        pos = pos.next\n",
    "\n",
    "      if not stack:\n",
    "        return None\n",
    "      new_head = stack[0]\n",
    "      new_head.next = None\n",
    "      pos = new_head\n",
    "      for i in range(1, len(stack)):\n",
    "        pos.next = stack[i]\n",
    "        pos = pos.next\n",
    "        pos.next = None\n",
    "      return new_head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeZeroSumSublists(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        if head == None:\n",
    "            return head\n",
    "        p = head\n",
    "        valSum = 0\n",
    "        while p:\n",
    "            valSum += p.val\n",
    "            p = p.next\n",
    "            if valSum == 0:\n",
    "                return self.removeZeroSumSublists(p)\n",
    "        head.next = self.removeZeroSumSublists(head.next)\n",
    "        return head\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeZeroSumSublists(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        if not head:\n",
    "            return None\n",
    "        s = 0\n",
    "        cur = head\n",
    "        while cur:\n",
    "            s += cur.val\n",
    "            if s == 0:\n",
    "                return self.removeZeroSumSublists(cur.next)\n",
    "            cur = cur.next\n",
    "        head.next = self.removeZeroSumSublists(head.next)\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeZeroSumSublists(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        nums = []\n",
    "        cur = head\n",
    "        while(cur):\n",
    "            nums.append(cur.val)\n",
    "            cur = cur.next\n",
    "        st = []\n",
    "        pre = 0\n",
    "        presum = [0]\n",
    "        for num in nums:\n",
    "            pre += num\n",
    "            presum.append(pre)\n",
    "        idxs = []\n",
    "        memo = {0:0}\n",
    "        for i in range(1,len(presum)):\n",
    "            if(presum[i] in memo):\n",
    "                idxs.append([memo[presum[i]], i-1])\n",
    "            memo[presum[i]] = i\n",
    "        if(len(idxs) == 0):\n",
    "            temp = nums[:]\n",
    "        else:\n",
    "            idxs.sort(key = lambda x:x[0])\n",
    "            start, end = idxs[0][0], idxs[0][1]\n",
    "            idxss = [[start, end]]\n",
    "            for i in range(1,len(idxs)):\n",
    "                if(idxs[i][0] > end):\n",
    "                    idxss.append([idxs[i][0], idxs[i][1]])\n",
    "                    start, end = idxs[i][0], idxs[i][1]\n",
    "            idxss = [[-1,-1]] + idxss\n",
    "            print(idxss)\n",
    "            temp = []\n",
    "            for i in range(1,len(idxss)):\n",
    "                s1, e1 = idxss[i-1][0], idxss[i-1][1]\n",
    "                s2, e2 = idxss[i][0], idxss[i][1]\n",
    "                temp += nums[e1+1:s2]\n",
    "            temp += nums[e2+1:]\n",
    "        result = ListNode(-1)\n",
    "        h = result\n",
    "        for num in temp:\n",
    "            h.next = ListNode(val=num)\n",
    "            h = h.next\n",
    "        return result.next\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeZeroSumSublists(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        nums = []\n",
    "        p = head\n",
    "        while p:\n",
    "            nums.append(p.val)\n",
    "            p = p.next\n",
    "        pre = list(accumulate(nums, initial=0))\n",
    "        nr = []\n",
    "        vis = {x: i for i, x in enumerate(pre)}\n",
    "        i, n = 0, len(pre)\n",
    "        while i < n:\n",
    "            p = vis[pre[i]]\n",
    "            if i != p:\n",
    "                nr.append((i, p))\n",
    "                i = p\n",
    "            i += 1\n",
    "\n",
    "        if len(nr) == 0:\n",
    "            return head\n",
    "        tmp = p = ListNode(-1, head)\n",
    "        i, j = -1, 0\n",
    "        left = nr[0][0] - 1\n",
    "        right = nr[0][1]\n",
    "        while p:\n",
    "            if i == left:\n",
    "                q = p\n",
    "                while right != i:\n",
    "                    p = p.next\n",
    "                    i += 1\n",
    "                q.next = p\n",
    "                j += 1\n",
    "                if j >= len(nr):\n",
    "                    break\n",
    "                else:\n",
    "                    left = nr[j][0] - 1\n",
    "                    right = nr[j][1]\n",
    "                    continue\n",
    "            p = p.next\n",
    "            i += 1\n",
    "        return tmp.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeZeroSumSublists(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        save_head = ListNode(next=head)\n",
    "        start = save_head\n",
    "\n",
    "        while start:\n",
    "            start.next = self.removeZeroOnce(start.next)\n",
    "            start = start.next\n",
    "            if start is None:\n",
    "                break\n",
    "            # print(start)\n",
    "        return save_head.next\n",
    "\n",
    "    def removeZeroOnce(self, head):\n",
    "        save_head, end = ListNode(next=head), head\n",
    "        start = save_head\n",
    "        sum_ = 0\n",
    "        \n",
    "        while end:\n",
    "            # print(start, end, sum_)\n",
    "            sum_ += end.val\n",
    "            end = end.next\n",
    "            \n",
    "            if sum_ == 0:\n",
    "\n",
    "                del start.next\n",
    "                start.next = end\n",
    "                \n",
    "        \n",
    "        return save_head.next\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeZeroSumSublists(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        valst = [0]\n",
    "        tmp = head\n",
    "        while tmp:\n",
    "            valst.append(tmp.val)\n",
    "            tmp = tmp.next\n",
    "        x = 0\n",
    "        todelst = set()\n",
    "        # accumval -> idx\n",
    "        accumlst = []\n",
    "        todeldict = defaultdict(int)\n",
    "        for i in range(len(valst)):\n",
    "            x += valst[i]\n",
    "            accumlst.append(x)\n",
    "            if x in todeldict:\n",
    "                tmplst = list(range(todeldict[x]+1, i+1))\n",
    "                for k in range(todeldict[x]+1, i+1):\n",
    "                    todelst.add(k)\n",
    "                    if accumlst[k] in todeldict and todeldict[accumlst[k]] in tmplst:\n",
    "                        todeldict.pop(accumlst[k])\n",
    "                    # key: accumlst[k], val: k\n",
    "            else:\n",
    "                todeldict[x] = i\n",
    "        #print(todelst)\n",
    "        dummy = ListNode(-1)\n",
    "        cur = dummy\n",
    "        idx = 1\n",
    "        while head:\n",
    "            #print(idx, head.val)\n",
    "            if idx not in todelst:\n",
    "                cur.next = head\n",
    "                cur = cur.next\n",
    "            head = head.next\n",
    "            idx += 1\n",
    "        cur.next = None\n",
    "        return dummy.next \n",
    "        \n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeZeroSumSublists(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        # 迭代\n",
    "        # 终止条件\n",
    "        if not head:\n",
    "            return head\n",
    "        # 定义临时节点，用于循环\n",
    "        temp = head\n",
    "        val = 0\n",
    "        while temp:\n",
    "            val += temp.val\n",
    "            if val == 0:\n",
    "                # 如果等于0，将后边链表返回\n",
    "                return self.removeZeroSumSublists(temp.next)\n",
    "            temp = temp.next\n",
    "        \n",
    "        # 迭代链表中后面的节点\n",
    "        head.next = self.removeZeroSumSublists(head.next)\n",
    "        return head\n",
    "        \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeZeroSumSublists(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        step = []\n",
    "        d = dict()\n",
    "        cur, dummy = head, ListNode()\n",
    "        i, prefix = 0, 0\n",
    "        d[0] = -1\n",
    "        while cur:\n",
    "            prefix += cur.val\n",
    "            step.append(0)\n",
    "            if prefix in d:\n",
    "                step[d[prefix] + 1] = i - d[prefix]\n",
    "            d[prefix] = i\n",
    "            i += 1\n",
    "            cur = cur.next\n",
    "\n",
    "        i, cur, ban = 0, dummy, 0\n",
    "        while head:\n",
    "            if ban == 0: ban = step[i]\n",
    "            if ban: ban -= 1\n",
    "            else:\n",
    "                cur.next = ListNode(head.val)\n",
    "                cur = cur.next\n",
    "            i += 1\n",
    "            head = head.next\n",
    "        return dummy.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeZeroSumSublists(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        while head:\n",
    "            s = 0\n",
    "            curr = head\n",
    "            while curr:\n",
    "                s += curr.val\n",
    "                if s == 0:\n",
    "                    head = curr.next\n",
    "                    break\n",
    "                curr = curr.next\n",
    "            else:\n",
    "                break\n",
    "        if head:\n",
    "            head.next = self.removeZeroSumSublists(head.next)\n",
    "        return head\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeZeroSumSublists(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        if not head: return None\n",
    "        res = 0\n",
    "        cursor = head\n",
    "        while cursor:\n",
    "            res += cursor.val\n",
    "            if res == 0:\n",
    "                return self.removeZeroSumSublists(cursor.next)\n",
    "            cursor = cursor.next\n",
    "        head.next = self.removeZeroSumSublists(head.next)\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeZeroSumSublists(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        acc = [0]\n",
    "        nds = []\n",
    "        cur = head\n",
    "        while cur!=None:\n",
    "            acc.append(acc[-1] + cur.val)\n",
    "            nds.append(cur)\n",
    "            cur = cur.next\n",
    "        #print(acc)\n",
    "        d = {}\n",
    "        for i in range(len(acc)):\n",
    "            a = acc[i]\n",
    "            d[a] = i\n",
    "        #print(d)\n",
    "\n",
    "        ret = None\n",
    "        prev = None\n",
    "\n",
    "        idx = 0\n",
    "        while idx<len(acc):\n",
    "            lst = d[acc[idx]]\n",
    "            if lst==idx:\n",
    "                if idx==len(nds):\n",
    "                    break\n",
    "                #print(nds[idx].val)\n",
    "                if ret==None:\n",
    "                    ret = nds[idx]\n",
    "                    prev = nds[idx]\n",
    "                else:\n",
    "                    prev.next = nds[idx]\n",
    "                    prev = nds[idx]\n",
    "                nds[idx].next = None\n",
    "                idx += 1\n",
    "            else:\n",
    "                idx = lst\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeZeroSumSublists(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        #  第一印象  前缀和\n",
    "        # 记录 正 负数 变化的位置（只有正负数变换才会 和=0）\n",
    "        # 退出条件 当前剩余 全部正  全部负\n",
    "        # 前缀和=0 删除 当前节点之前所有  保留当前节点之后  \n",
    "        # 出现重复的前缀和时，删除 第一次出现之后 到重复位置的部分 \n",
    "        # 遇到负数（正负切换）前推（当前负数向前算前缀和）\n",
    "        ans=[0]\n",
    "        cnt={}\n",
    "        cnt[0]=0\n",
    "        x=head\n",
    "        index=1\n",
    "        while x:\n",
    "            ans.append(x.val+ans[-1])\n",
    "            # print(ans[-1],ans[-1] in cnt.keys() and cnt[ans[-1]]!=-1)\n",
    "            if ans[-1] in cnt.keys() and cnt[ans[-1]]!=-1:\n",
    "                # print(cnt[ans[-1]]+1,ans[cnt[ans[-1]]+1:-1])\n",
    "                index-=len(ans[cnt[ans[-1]]+1:-1])\n",
    "                for i in ans[cnt[ans[-1]]+1:-1]:\n",
    "                    # print(\"i=\",i)\n",
    "                    cnt[i]=-1\n",
    "                ans=ans[:cnt[ans[-1]]+1]\n",
    "                \n",
    "            else:\n",
    "                cnt[ans[-1]]=index\n",
    "                index+=1\n",
    "            x=x.next\n",
    "            \n",
    "            # print(\"ans=\",ans,\"\\ncnt=\",cnt,\"\\n\",\"index=\",index,\"\\n\")\n",
    "\n",
    "        \n",
    "        if ans==[0]:\n",
    "            return None\n",
    "        res=ListNode()\n",
    "        x=res\n",
    "        # print(res,x)\n",
    "\n",
    "        for i in range(1,len(ans)):\n",
    "            x.val=ans[i]-ans[i-1]\n",
    "            if i<len(ans)-1:\n",
    "                x.next=ListNode()\n",
    "                x=x.next\n",
    "            # print(i,res)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeZeroSumSublists(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        if not head:\n",
    "            return None\n",
    "        sum=0\n",
    "        cursor=head\n",
    "        while cursor:\n",
    "            sum+=cursor.val\n",
    "            if sum==0:\n",
    "                return self.removeZeroSumSublists(cursor.next)\n",
    "            cursor=cursor.next\n",
    "        head.next=self.removeZeroSumSublists(head.next)\n",
    "        return head\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeZeroSumSublists(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        # 迭代\n",
    "        # 终止条件\n",
    "        if not head:\n",
    "            return head\n",
    "        # 定义临时节点，用于循环\n",
    "        temp = head\n",
    "        val = 0\n",
    "        while temp:\n",
    "            val += temp.val\n",
    "            if val == 0:\n",
    "                # 如果等于0，将后边链表返回\n",
    "                return self.removeZeroSumSublists(temp.next)\n",
    "            temp = temp.next\n",
    "        \n",
    "        # 迭代链表中后面的节点\n",
    "        head.next = self.removeZeroSumSublists(head.next)\n",
    "        return head\n",
    "        \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "# 递归\n",
    "class Solution:\n",
    "    def removeZeroSumSublists(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        if not head:\n",
    "            return head\n",
    "        p = head\n",
    "        total = 0\n",
    "        while p:\n",
    "            total += p.val\n",
    "            if total == 0:\n",
    "                return self.removeZeroSumSublists(p.next)\n",
    "            p = p.next\n",
    "        head.next = self.removeZeroSumSublists(head.next)\n",
    "        return head\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeZeroSumSublists(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        head_list = []\n",
    "        while head:\n",
    "            head_list.append(head.val)\n",
    "            head = head.next\n",
    "\n",
    "        dp = []\n",
    "        index = 0\n",
    "        while index<len(head_list):\n",
    "            if head_list[index] ==0:\n",
    "                head_list.pop(index)\n",
    "                continue\n",
    "\n",
    "            zero_dp_index = None\n",
    "            for i in range(len(dp)-1, -1,-1):\n",
    "                dp[i][1] += head_list[index]\n",
    "                if dp[i][1]==0:\n",
    "                    zero_dp_index = i\n",
    "            if zero_dp_index is not None:\n",
    "                head_list = head_list[:dp[zero_dp_index][0]]+head_list[index+1:]\n",
    "                index = dp[zero_dp_index][0]\n",
    "                dp = dp[:dp[zero_dp_index][0]]\n",
    "            else:\n",
    "                dp.append([index,head_list[index]])\n",
    "                index += 1\n",
    "            # print(head_list)\n",
    "            # print(dp,index)\n",
    "        if not head_list:\n",
    "            return None\n",
    "\n",
    "        new_head = ListNode(val=head_list.pop(0))\n",
    "        cur_node = new_head\n",
    "        while head_list:\n",
    "            cur_node.next = ListNode(val=head_list.pop(0))\n",
    "            cur_node = cur_node.next\n",
    "        return new_head\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeZeroSumSublists(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        nums = []\n",
    "        while head:\n",
    "            nums.append(head.val)\n",
    "            head = head.next\n",
    "\n",
    "        while True:\n",
    "            sm = [0]\n",
    "            for n in nums:\n",
    "                sm.append(sm[-1] + n)\n",
    "            # print(sm)\n",
    "            dc = {}\n",
    "            for i, c in enumerate(sm):\n",
    "                if dc.get(c) is not None:\n",
    "                    l, r = dc[c], i\n",
    "                    break\n",
    "                else:\n",
    "                    dc[c] = i\n",
    "            else:\n",
    "                break\n",
    "            nums = nums[:l] + nums[r:]\n",
    "            # print(nums)\n",
    "        head = ListNode()\n",
    "        h = head\n",
    "        for n in nums:\n",
    "            h.next = ListNode(n)\n",
    "            h = h.next\n",
    "        return head.next"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
